package greedy_algorithm.nowcoder.easy;

import java.util.Scanner;

/**
 * @author Stark
 * @description 排序子序列
 * 题目链接：https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471?
 * orderByHotValue=1&page=1&onlyReference=false
 * @date 2022/4/18 20:23
 **/
public class SortSubsequence {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            int n = scanner.nextInt();
            //多开辟一个空间,方便最后一个数据进行比较
            //数据要求1-10^9,最有一个元素为0,不影响结果
            int[] arr = new int[n + 1];
            for(int i = 0;i < n;i++){
                arr[i] = scanner.nextInt();
            }
            //保存排序子序列的个数
            int count = 0;
            int i = 0;
            while(i < n){
                if(arr[i] < arr[i + 1]){
                    //进入非递减序列的判断
                    for(;i < n && arr[i] <= arr[i + 1];i++);
                    //走出了非递减序列,count++
                    count++;
                    //i往后移动一位,一位i还在非递减序列的
                    //加一进入后序的数据判断
                    i++;
                }else if(arr[i] == arr[i + 1]){
                    //跳过相同的元素
                    for(;i < n && arr[i] == arr[i + 1];i++);
                    i++;
                }else{
                    //进入非递增序列的判断
                    for(;i < n && arr[i] >= arr[i + 1];i++);
                    count++;
                    i++;
                }
            }
            System.out.println(count);
        }
    }
}
